package com.wxweven.algorithm.string;

import org.junit.Assert;
import org.junit.Test;

import java.util.HashSet;
import java.util.Set;

public class LC03最长不重复子串 {
    /*
     * Given a string, find the length of the longest substring without repeating characters.
     *
     * Example 1:
     * Input: "abcabcbb"
     * Output: 3
     * Explanation: The answer is "abc", with the length of 3.

     * * Example 2:
     * Input: "bbbbb"
     * Output: 1
     * Explanation: The answer is "b", with the length of 1.
     *
     * Example 3:
     * Input: "pwwkew"
     * Output: 3
     * Explanation: The answer is "wke", with the length of 3.
     * Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
     */

    /**
     * 视频讲解：https://www.youtube.com/watch?v=fBiiKy8kwaY
     * 基本思路：双指针；有别于数组的双指针（left往右, right往左)
     * 字符串的双指针，通常是left起点，然后i往后遍历
     */

    @Test
    public void test() {
        int res1 = lengthOfLongestSubstring("abcabcbb");
        int res2 = lengthOfLongestSubstring("bbbbb");
        int res3 = lengthOfLongestSubstring("pwwkew");

        Assert.assertEquals(res1, 3);
        Assert.assertEquals(res2, 1);
        Assert.assertEquals(res3, 3);
    }

    public static int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        /*
         * 假设str = "pwkweak", set 刚开始<p,w,k>
         * 这时候再进来 w，就会有重复了，所以得重新开始算不重复的最大值，
         * 那肯定要从 pw 后面的 k 算起，不然还是会有重复的，所以set得把之前加入的p w删除掉
         * 那怎么删除呢？维护另外一个变量j, 从0开始，每次+1，就是把set最开始加入的元素删除
         */

        char[] chars = s.toCharArray();
        Set<Character> charSet = new HashSet<>();
        int max = 0;
        int j = 0;

        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];

            // 当前重复字符为c
            while (charSet.contains(c)) {
                // 循环的目的是把已经加入到set的当前重复字符和重复字符之前的字符都从set中删除
                charSet.remove(chars[j]);
                j++;
            }

            // 下面两步是每次循环都需要做的
            charSet.add(c);
            max = Math.max(max, charSet.size());

        }

        return max;
    }
}
